package com.mystudy.leetcode.problem.link.p_876;

import com.mystudy.leetcode.base.ListNode;
import com.mystudy.leetcode.base.ListNodeUtils;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @program: infoalgorithm
 * @description: 求链表的中间节点
 * @author: zhouzhilong
 * @create: 2019-07-04 09:46
 **/
public class Solution {

    private static final Logger LOGGER = LoggerFactory.getLogger(Solution.class);

    long startTime = 0L;
    long endTime = 0L;


    @Before
    public void before() {
        startTime = System.nanoTime();
    }

    @Test
    public void test() {
        ListNode listNode = ListNodeUtils.generateLinkList(new int[]{1, 2, 3, 4, 5, 6, 7});
        ListNode listNode1 = middleNode(listNode);
        ListNodeUtils.show(listNode1);
    }

    @After
    public void after() {
        endTime = System.nanoTime();
        double cost = (endTime - startTime) / 1000000.0;
        LOGGER.debug("cost = [{} ms ]",cost);
    }




    /**
     * 使用快慢指针法
     */
    public ListNode middleNode(ListNode head) {
        ListNode fast = head.next;
        ListNode lazy = head;
        while (fast != null) {
            lazy = lazy.next;
            fast = (fast.next == null || fast.next.next == null) ? null : fast.next.next;
        }
        return lazy;
    }

    /**
     * 使用循环
     */
    public ListNode middleNode2(ListNode head) {
        int count = 0;
        ListNode[] nodes = new ListNode[100];
        for (ListNode cur = head; cur != null; cur = cur.next) {
            nodes[count] = cur;
            count++;
        }
        return nodes[(count / 2)];

    }

}
